Андрей и Олег очень любят работать, но у них нет своего офиса. Поэтому они работают в коворкингах.
Всего в доме $$$n$$$ коворкингов, расположенных на одной прямой. $$$i$$$-й коворкинг имеет координату $$$a_i$$$ на этой прямой. Никакие два коворкинга не находятся в одной точке. У каждого коворкинга есть режим работы: $$$i$$$-й коворкинг открывается в момент времени $$$o_i$$$ и закрывается в момент времени $$$c_i$$$.
Андрей и Олег хотят провести максимально возможное время в коворкингах. За единицу времени они могут переместиться влево либо вправо, изменив свою координату на -1 или 1 соответственно. Помогите им найти максимальное время пребывания в коворкингах. В момент времени 0 они находятся в точке с координатой 0.
В первой строке задано одно число $$$n \ (1 \leq n \leq 10^5)$$$ — количество коворкингов. В каждой из следующих $$$n$$$ строк находится по три целых числа $$$a_i, o_i, c_i \ (1 \leq a_i \leq 10^8, 1 \leq o_i \lt c_i \leq 10^8)$$$ — координата $$$i$$$-го коворкинга, время открытия и закрытия $$$i$$$-го коворкинга.
Выведите одно число — максимальное время пребывания Андрея и Олега в коворкингах.
В этой задаче проверка осуществляется по подгруппам. Баллы за первую и вторую подгруппы начисляются в случае прохождения всех тестов в них. Подгруппы 3 и 4 содержат 10 тестов, каждый из которых оценивается в 3 балла.
Обозначим максимальное значение $$$c_i$$$ по всем $$$i$$$ от 1 до $$$n$$$ как $$$C$$$.
Обозначим максимальное значение $$$a_i$$$ по всем $$$i$$$ от 1 до $$$n$$$ как $$$A$$$.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи |
| 1 | 30 | $$$n \leqslant 1000, A, C \leqslant 10000$$$ | - |
| 2 | 40 | $$$n \leqslant 1000$$$ | 1 |
| 3 | 18 | $$$A, C \leqslant 2 \cdot 10^5$$$ | 1, 2 |
| 4 | 12 | нет | 1, 2, 3 |
21 1 62 5 8
6
44 5 81 11 166 11 158 17 19
9
В первом примере оптимальной стратегией для Олега и Андрея будет следующая: с самого начала (момент 0, координата 0) им нужно выдвинуться в координату 1 (в первый коворкинг). Они придут туда в момент времени 1. С момента времени 1 до момента 6 они пробудут в первом коворкинге, после чего он закроется. В момент 6 Андрей и Олег начнут движение из координаты 1 в координату 2, во второй коворкинг. Они придут в коворкинг в момент времени 7, и он закроется в 8. Итоговый ответ: $$$(6 - 1) + (8 - 7) = 5 + 1 = 6$$$.